# 第1节镖局运镖-图的最小生成树
# kruskal算法
# 所有边的权值加起来最小，即是最小生成树
class Edge:
    """存储边的关系"""

    def __init__(self):
        self.u = 0
        self.v = 0
        self.w = 0


e = [Edge() for i in range(0, 11)]
n, m = 0, 0
# 并查集需要用到的一些变量
f = [0 for i in range(0, 8)]
s, count = 0, 0


def quick_sort(left, right):
    i, j = 0, 0
    edge = Edge()
    if left > right:
        return
    i = left
    j = right
    while i != j:
        # 顺序很重要，先从右边开始找
        while (e[j].w > e[left].w) and (i < j):
            j -= 1
        # 从左边开始找
        while (e[i].w < e[left].w) and (i < j):
            i += 1
        if i < j:
            t = e[i]
            e[i] = e[j]
            e[j] = t
    # 最终将基准归位，将left和i互换
    t = e[left]
    e[left] = e[i]
    e[i] = t
    quick_sort(left, i - 1)
    quick_sort(i + 1, right)


# 并查集寻找祖先的函数
def get_f(v):
    if f[v] == v:
        return v
    else:
        f[v] = get_f(f[v])
        return f[v]


# 并查集合并两子集的函数
def merge(v, u):
    t1 = get_f(v)
    t2 = get_f(u)
    if t1 != t2:
        f[t2] = t1
        return 1
    return 0


if __name__ == '__main__':
    n, m = 6, 9
    a = [[2, 4, 11], [3, 5, 13], [4, 6, 3], [5, 6, 4], [2, 3, 6], [4, 5, 7], [1, 2, 1], [3, 4, 9], [1, 3, 2]]
    # 初始化并查集
    for i in range(1, 8):
        f[i] = i
    # 初始化边
    for i, v in enumerate(a):
        e[i + 1].u = v[0]
        e[i + 1].v = v[1]
        e[i + 1].w = v[2]

    quick_sort(1, m)

    # kruskal算法核心部分
    for i in range(1, m + 1):
        # 判断一条边的两个点是否已经连通，即判断是否在一个集合中
        if merge(e[i].u, e[i].v):
            count += 1
            s = s + e[i].w
        if count == n - 1:
            break

    print(s)
